//32 最长有效括号
//给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。 
//
// 示例 1: 
//
// 输入: "(()"
//输出: 2
//解释: 最长有效括号子串为 "()"
// 
//
// 示例 2: 
//
// 输入: ")()())"
//输出: 4
//解释: 最长有效括号子串为 "()()"
// 
// Related Topics 字符串 动态规划


package leetcode.editor.cn;

import java.util.Deque;
import java.util.LinkedList;

/**
 * 有左右两次遍历的方法。精髓还没掌握
 */
public class A32LongestValidParentheses {
    public static void main(String[] args) {
        Solution solution = new A32LongestValidParentheses().new Solution();
        System.out.println("佛祖保佑");
        System.out.println("\uD80C\uDC09\uD80C\uDC02\uD80C\uDC03\uD80C\uDC10");

    }

    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * 解答成功:
     * 执行耗时:3 ms,击败了58.97% 的Java用户
     * 内存消耗:39.7 MB,击败了9.52% 的Java用户
     */
    class Solution {
        public int longestValidParentheses(String s) {
            Deque<Integer> stack = new LinkedList<>();
            int max = 0;
            stack.push(-1);
            for (int i = 0; i < s.length(); i++) {
                if (s.charAt(i) == '(') {
                    stack.push(i);
                } else if (s.charAt(i) == ')') {
                    stack.pop();//消消乐
                    if (stack.size() == 0) {// 不小心消过头了，不能去算max值
                        // 留下这个右括号，它是新的左边界
                        stack.push(i);
                    } else {//消掉的都是左括号，所以要算
                        max = Math.max(max, i - stack.peek());// 有当前的i值，有左边界
                    }
                }
            }
            return max;
        }
    }
//leetcode submit region end(Prohibit modification and deletion)

}
